The invention generally resides in flow control mechanisms of telecommunications network. In particular, it is directed to scheduling of traffic classes at a node of an ATM network and more specifically to the traffic scheduling which is based on the rates allocated to each class of the traffic.
ATM networks are multimedia networks which handle a mixture of traffic classes with diverse connection requirements. The networks-employ a variety of traffic control and/or network management techniques to ensure that the networks meet the connection requirements. In FIG. 1, a number of traffic classes a to d are buffered in separate queues 10 and a controller 12 (or scheduler) accesses the queues for outputting in a certain order so that an output link 14 of fixed capacity is shared by the traffic classes. Throughout the specification, xe2x80x9cclassxe2x80x9d or xe2x80x9ctraffic classxe2x80x9d is used to indicate a category of traffic in accordance with a certain descriptor. A class therefore may represent the traffic of one connection or may contain different connections, all having a common descriptor, i.e. all the cells in a class are buffered in the same queue. Therefore, there are as many queues as there are classes and the scheduler may be described as a queue controller. The classes may share the link according to one of many policies, such as strict priority, a fixed-rate per class, a guaranteed minimum rate per class, etc. In any of these policies, the maximum number of cells that a queue may transfer to the link in a single transaction may be limited to a predetermined bound. These control mechanisms are sometimes called scheduling mechanisms. In the priority based scheduling mechanism, one class of traffic will always be served before the other as long as there are cells to send. Satisfying the delay and loss requirements of the lower priority class may not be possible due to the traffic behaviour in the high priority class. When more priorities are added, satisfying delay and loss guarantees of each class becomes progressively more difficult. For example, FIG. 2 shows the priority scheduler 20 in which there are four queues 22 for four priority classes, a to d in the descending order. Relative arrival 24 of cells for each class is also shown in the figure. Cells are stored in respective queues when they arrive and the priority scheduler serves the queues according to the degree of priority. FIG. 3 is a series of charts showing conditions of the queues and a selection of a cell for output by a priority scheduler at each successive output timeslot (cell interval). At timeslot 1, cell a1 is selected because of its highest priority. At timeslot 2, however, cell b1 is selected because cell a3 is yet to arrive and b1 is the highest priority cell among cells stored in the queues. The sequence continues in a similar fashion. The output traffic 30 on the link would consists of a series of ATM cell as shown at the bottom of the figure. As seen in the figure, class d therefore must wait until the first three classes are empty before being allowed to send traffic.
A rate scheduler selects queues according to criteria based on the preset bandwidth allocation to each class, i.e. the link bandwidth is divided among different classes of traffic based on the respective rate of traffic for each class. For example in FIG. 4, classes a to c are given xc2xc (in other words, one in every four cells at the most) of the total capacity of the link and class d has ⅕ of the capacity. This gives each class a number of dedicated opportunities to send cells and limits the impact of higher priority classes. In other words, with a rate scheduler, no queue has xe2x80x9cpriorityxe2x80x9d over another. Interference (competition or contention) comes from all queues now, not just from higher priority ones. However the interference is lessened by the rate limits of the queues, and changing the assigned rates offers a way to manage the interference, thus improving isolation. Similar to FIG. 3, FIG. 5 shows a series of chart showing conditions of queues and selection of a cell for outputting at each successive output timeslot. In this example, cell arrival is the same as that shown in FIG. 2. At timeslots 1 and 2, cells a1 and b1 are selected. At timeslot 3, however, although the highest priority queue contains cell a3, the scheduler cannot send the cell out because class a has used up its allocated bandwidth when it sent out cell a1 two timeslots earlier. In other words, queue a must wait for at least three timeslots before it is allowed to send a cell. The output traffic profile on the link is therefore as shown at the bottom of the figure. Improved isolation of classes allows a better chance at meeting delay and loss guarantees for each class. This leads to simpler call admission control algorithms and higher link utilization. A programmable rate mechanism allows the scheduler to track the changing traffic profile of the link. This could be controlled by software and updated every time a connection is created/destroyed. While the rate based scheduling mechanism operates in principle as described above, there are different schemes for implementing the general concept. The invention is concerned with efficient allocation of a specified bandwidth to each traffic class.
It is therefore an object of the invention to provide a method of and apparatus for scheduling packet traffic onto an output link.
It is another object of the invention to provide a method of and apparatus for scheduling packet traffic in which the scheduling is based upon the bandwidth allocation among various classes of traffic.
It is still an object of the invention to provide a method of and apparatus for scheduling packet traffic in which the scheduling is based on indexing a scheduling table which indicates the next class of traffic to be serviced and updating the table according to the bandwidth allocation of the class.
It is yet another object of the invention to provide a method of and apparatus for scheduling packet traffic in which the classes in the same timeslot are linked in the table.
It is a further object of the invention to provide a method of and apparatus for scheduling ATM traffic onto an output link.
Briefly stated, the invention resides in a packet network in which a node receives a plurality of traffic classes and outputs them to an output link. According to one aspect, the invention is directed to a method of scheduling the traffic classes. The method comprises steps of buffering cells of each traffic class in a respective queue, assigning reference numbers, Tnext, to traffic classes buffered in the queues and creating one or more linked lists of traffic classes, each of which has traffic classes with a similar scheduled departure time determined from Tnext. The method includes further steps of outputting cells to the output link from the queues according to the scheduled departure time of the linked list of traffic classes and updating the Tnext according to the bandwidth allocated to each class.
According to another aspect, the invention is directed to an apparatus for scheduling the traffic classes in a packet network in which a node receives a plurality of traffic classes and outputs them to an output link. The apparatus comprises a plurality of queues, each queue for buffering cells of each traffic class and a class data structure containing reference numbers, Tnext, assigned to traffic classes and one or more linked lists of traffic classes, each list having traffic classes with a similar scheduled departure time determined from Tnext. The apparatus further includes a reference counter for indexing the linked lists of traffic classes according to their scheduled departure times and selecting one linked list for outputting cells to the output link according to its scheduled departure time , and a link/parser for updating the Tnext according to the bandwidth allocated to each class and for linking classes into the linked lists of the appropriate timeslots.